package com.xsomnus.data_structures.searching;

/**
 * @author @xsomnus666_xiawenye★
 * @since 2019/7/18 0018 17:31
 * - 才需学也,学需静也/非淡泊无以明志，非宁静无以致远
 * <desc>
 * 堆
 * </desc>
 */
public class MaxHeap<E extends Comparable<E>> {

    private Array<E> data;


    // 默认层数是4层
    private static final int defaultHeapSize = 2 << 4 - 1;

    public MaxHeap() {
        data = new Array<>(defaultHeapSize);
    }

    public void delete(E e) {
        final int index = data.find(e);
        if (index == -1) {
            throw new IllegalArgumentException("element " + e + " is not exist.");
        }

        int size = data.getSize();
        data.set(index, data.get(size - 1));
        data.remove(size - 1);

        if (data.getSize() > 1) {
            siftDown(index);
        }
    }

    private void siftDown(int k) {
        while (leftChild(k) < data.getSize()) {
            int j = leftChild(k);
            if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
                j++;
            }
            if (data.get(k).compareTo(data.get(j)) > 0) {
                break;
            }

            data.swap(k, j);
            k = j;
        }
    }

    public void add(E e) {
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }

    private void siftUp(int k) {
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
            data.swap(k, parent(k));
            k = parent(k);
        }
    }

    // 返回左孩子节点的索引
    private int leftChild(int index) {
        return index * 2 + 1;
    }

    // 返回右孩子的节点的索引
    private int rightChild(int index) {
        return index * 2 + 2;
    }

    // 返回父节点的索引
    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index 0 doesn't have parent.");
        }
        return (index - 1) / 2;
    }

    @Override
    public String toString() {
        return "MaxHeap{" +
                "data=" + data +
                '}';
    }
}
